package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-06
 */
public class 有重复项数字的所有排列 {
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> arrayLists = permuteUnique(new int[]{1, 1, 2});

        System.out.println(arrayLists);

    }

    public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        if (num == null) {
            return new ArrayList<>();
        }
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Permutation(num, 0, result);
        return result;
    }

    private static void Permutation(int[] chars, int index, ArrayList<ArrayList<Integer>> result) {
        if (index == chars.length) {
            ArrayList<Integer> arrayList = new ArrayList(Arrays.asList(chars));
            result.add(arrayList);

            System.out.println(arrayList.toArray());
        }
        for (int i = index; i < chars.length; i++) {

            swap(chars, i, index);
            Permutation(chars, index + 1, result);
            if (i > 0 && chars[i] == chars[i - 1]) {
                continue;
            }
            swap(chars, i, index);

        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
